//<p>数字 <code>n</code>&nbsp;代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 <strong>有效的 </strong>括号组合。</p>
//
//<p>&nbsp;</p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 3
//<strong>输出：</strong>["((()))","(()())","(())()","()(())","()()()"]
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>n = 1
//<strong>输出：</strong>["()"]
//</pre>
//
//<p>&nbsp;</p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 &lt;= n &lt;= 8</code></li>
//</ul>
//<div><div>Related Topics</div><div><li>字符串</li><li>动态规划</li><li>回溯</li></div></div><br><div><li>👍 2626</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * @author DY Rising
 * @date 2022-05-10 14:32:28
 */
public class P22_GenerateParentheses{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P22_GenerateParentheses().new Solution();
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> rtns = new ArrayList<>();
        this.generateStr(n, n, new StringBuilder(), rtns, "");
        return rtns;
    }

    /**
     * 深度优先，回溯
     * 生出左支条件：左括号剩余数量大于0
     * 生出右支条件：左括号剩余数量小于有括号剩余数量
     * @param left
     * @param right
     * @param stringBuilder
     * @param rtns
     */
    public void generateStr(int left, int right, StringBuilder stringBuilder, List<String> rtns, String ch) {
        if (left < 0 || right <0) return;
        stringBuilder.append(ch);
        if (left == 0 && right == 0) rtns.add(stringBuilder.toString());
        if (left > 0 )
            generateStr(left - 1, right, stringBuilder, rtns, "(");
        if (left < right)
            generateStr(left, right - 1, stringBuilder, rtns, ")");
        if (stringBuilder.length() > 0) stringBuilder.deleteCharAt(stringBuilder.length() - 1);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
